O que é grupo nd?

Grupo ND (Non-Deterministic Polynomial time)

Em teoria da complexidade computacional, o grupo ND (tempo polinomial não-determinístico) é uma classe de complexidade que contém os problemas de decisão para os quais as soluções podem ser verificadas em tempo polinomial. Em outras palavras, se a resposta para uma instância do problema é "sim", então existe uma "prova" (também chamada de "certificado") que pode ser verificada em tempo polinomial determinístico.

Conceitos Chave:

• Verificação Polinomial: A ideia central do grupo ND é a verificação eficiente de soluções. Mesmo que encontrar uma solução possa ser difícil, provar que uma solução é correta deve ser relativamente fácil. Isto é, o algoritmo de verificação deve ser executado em tempo polinomial. Veja mais sobre Algoritmo%20Polinomial.

• Não-Determinismo: O "não-determinístico" em ND refere-se à maneira teórica como uma máquina de Turing hipotética poderia "adivinhar" a prova correta. Essencialmente, a máquina tentaria todas as provas possíveis simultaneamente (paralelamente). Se alguma dessas "adivinhações" levar a uma verificação positiva em tempo polinomial, então a resposta é "sim". Esta não é a maneira como computadores reais funcionam, mas é uma abstração útil para definir a complexidade do problema. Veja mais sobre Máquina%20de%20Turing.

• NP-Completo: Dentro de ND existe um subconjunto de problemas conhecidos como NP-Completo. Estes são os problemas "mais difíceis" em ND, no sentido de que se um problema NP-Completo pudesse ser resolvido em tempo polinomial, então todos os problemas em ND poderiam ser resolvidos em tempo polinomial.

• NP-Difícil (NP-Hard): Problemas NP-Difícil são pelo menos tão difíceis quanto os problemas mais difíceis em ND (NP-Completo). No entanto, ao contrário dos problemas NP-Completos, problemas NP-Difíceis não precisam estar em ND. Isso significa que eles podem não ter um algoritmo de verificação em tempo polinomial.

Exemplos:

• O Problema do Caixeiro Viajante (PCV): Dado uma lista de cidades e as distâncias entre cada par de cidades, existe um tour que visita cada cidade exatamente uma vez e retorna à cidade inicial com um custo total inferior a k? Se alguém lhe desse um tour, você poderia facilmente verificar em tempo polinomial se o tour é válido (visita cada cidade uma vez) e se o custo total é menor que k.

• O Problema da Satisfatibilidade Booleana (SAT): Dada uma fórmula booleana, existe uma atribuição de valores verdadeiros às variáveis que tornam a fórmula verdadeira? Se alguém lhe desse uma atribuição, você poderia facilmente verificar em tempo polinomial se a atribuição satisfaz a fórmula.

Importância:

A classe ND é extremamente importante na teoria da computação. A questão de se P = ND é um dos problemas não resolvidos mais importantes na ciência da computação e na matemática. Se P = ND, isso significaria que cada problema cuja solução pode ser verificada rapidamente (em tempo polinomial) também pode ser resolvido rapidamente (em tempo polinomial). A maioria dos especialistas acredita que P ≠ ND, mas nenhuma prova foi encontrada até agora. O problema P versus ND tem um prêmio de um milhão de dólares oferecido pelo Clay Mathematics Institute.